/* 0. 代码随想录 */
int* path;         // step 1# 存放当前子集路径
int pathTop;       // step 2# 当前子集的元素个数
int** ans;         // step 3# 最终存放所有子集的二维数组
int ansTop;        // step 4# 当前已经收集的子集个数
int* length;       // step 5# 存放每个子集中元素的个数（对应每一行的长度）

// step 6# 将当前 path 中的内容复制到 ans 中，形成一个新的子集
void copy() {
    int* tempPath = (int*)malloc(sizeof(int) * pathTop); // step 6.1# 分配空间复制当前子集
    int i;
    for(i = 0; i < pathTop; i++) {
        tempPath[i] = path[i]; // step 6.2# 复制 path 内容到新数组
    }
    ans = (int**)realloc(ans, sizeof(int*) * (ansTop + 1)); // step 6.3# 扩展 ans 空间
    length[ansTop] = pathTop;  // step 6.4# 记录该子集的长度
    ans[ansTop++] = tempPath;  // step 6.5# 存入 ans 并更新 ansTop
}

// step 7# 回溯函数，用于构建所有子集
void backTracking(int* nums, int numsSize, int startIndex) {
    // note 1### 空集的收集在这里完成的
    copy();  // step 7.1# 收集当前子集（包括空集）
    
    if(startIndex >= numsSize) return; // step 7.2# 终止条件：索引越界，返回
    
    for(int j = startIndex; j < numsSize; j++) {
        path[pathTop++] = nums[j];           // step 7.3# 选择当前元素加入子集
        backTracking(nums, numsSize, j + 1); // step 7.4# 递归构造后续子集
        pathTop--;                           // step 7.5# 回溯，撤销选择
    }
}

// step 8# 主函数，初始化变量并返回所有子集
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    path = (int*)malloc(sizeof(int) * numsSize); // step 8.1# 分配 path 空间
    ans = (int**)malloc(0);                      // step 8.2# 初始化 ans 为 NULL 空数组
    length = (int*)malloc(sizeof(int) * 1500);   // step 8.3# 预分配长度数组（上限设置为1500）
    ansTop = pathTop = 0;                        // step 8.4# 初始化指针索引

    backTracking(nums, numsSize, 0);             // step 8.5# 调用回溯生成所有子集

    *returnSize = ansTop;                        // step 8.6# 设置返回子集个数
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop); // step 8.7# 分配列长度数组
    for(int i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = length[i];     // step 8.8# 拷贝每个子集的长度
    }

    return ans;                                  // step 8.9# 返回所有子集
}

/* 1. 20250424 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

/*
    step 1# 回溯参数：nums（输入数组）、startIndex（当前递归起点）
    step 2# 终止条件：递归无显式终止，而是控制 for 循环范围；只有初始 path 不递归
    step 3# 本层逻辑：每加入一个元素就保存当前 path 到结果集中（包括空集）
*/

// step 0# 全局变量定义
int **ans;      // 保存所有子集结果的二维数组
int *ansLen;    // 每个子集的元素个数
int ansTop;     // 当前结果集大小
int *path;      // 当前构造的子集路径
int pathTop;    // 当前路径中元素数量

// step 4# 将当前 path 复制并保存到结果数组 ans 中
void savePathToAns() {
    int *temp = (int *)malloc(sizeof(int) * pathTop);
    for (int i = 0; i < pathTop; i++) {
        temp[i] = path[i];
    }
    ans[ansTop] = temp;
    ansLen[ansTop++] = pathTop;
}

// step 5# 回溯函数主体
void backtracking(int *nums, int numsSize, int startIndex) {
    if (startIndex >= numsSize) return;  // step 5.1# 终止条件（其实可省略）

    for (int i = startIndex; i < numsSize; i++) {
        path[pathTop++] = nums[i];      // step 5.2# 选择当前数字加入 path
        savePathToAns();                // step 5.3# 保存当前 path 为一个子集
        backtracking(nums, numsSize, i + 1);  // step 5.4# 向后递归，构造后续子集
        pathTop--;                      // step 5.5# 回溯，移除上一步加入的元素
    }
}

// step 6# 主函数：初始化 + 启动回溯
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    ans = (int **)malloc(sizeof(int *) * 40000);     // step 6.1# 分配结果数组空间
    path = (int *)malloc(sizeof(int) * 40000);       // step 6.2# 分配路径数组空间
    ansLen = (int *)malloc(sizeof(int) * 40000);     // step 6.3# 分配每个子集长度数组
    ansTop = pathTop = 0;

    savePathToAns();            // step 6.4# 先保存空集（什么都不选）
    backtracking(nums, numsSize, 0);  // step 6.5# 启动回溯

    *returnSize = ansTop;

    *returnColumnSizes = (int *)malloc(sizeof(int) * ansTop);  // step 6.6# 输出每个子集长度
    for (int i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = ansLen[i];
    }

    return ans;
}
